# Definition for a binary tree node.
import collections
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# class Solution(object):
#     def isBalanced(self, root):
#         """
#         :type root: TreeNode
#         :rtype: bool
#         """
#         if not root:
#             return True
#         elif (abs(self.heigh(root.left) - self.heigh(root.right)) <= 1):
#             return self.isBalanced(root.left) and self.isBalanced(root.right)
#         else:
#             return False
#
# #         先求二叉树高度
#     def heigh(self,node):
#         height = 0
#         if node:
#             llevel = self.heigh(node.left)
#             print(llevel)
#             rlevel = self.heigh(node.right)
#             height = max(llevel,rlevel)+1
#         return height
class Solution(object):
    def isBalanced(self, root):
        return self.getDepth(root, 0) != -1

    def getDepth(self, node, depth):
        if node is None:
            return depth

        depth += 1

        l_d = self.getDepth(node.left, depth)
        if l_d == -1:
            return -1

        r_d = self.getDepth(node.right, depth)
        if r_d == -1:
            return -1

        if abs(r_d - l_d) > 1:
            return -1
        return max(l_d, r_d)

m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(2)
m1.left.left = TreeNode(2)
# m1.left.left.left = TreeNode(3)
# m1.left.left.right = TreeNode(3)
# m1.left.left.left.left = TreeNode(4)
# m1.left.left.left.right = TreeNode(4)
m1.right.right = TreeNode(2)
s = Solution()

t = s.isBalanced(m1)
print(t)
